11259. Минимальная триангуляция

Вам задан правильный многоугольник из n вершин, пронумерованных от 1 до n против часовой стрелки. Триангуляция данного многоугольника – это набор треугольников такой, что каждая вершина любого из треугольников является вершиной первоначального многоугольника, не существует пары треугольников имеющих положительную площадь пересечения, и площадь объединения треугольников равна площади многоугольника. Вес триангуляции – это сумма весов треугольников из которых она состоит, где весом треугольника является произведение меток его вершин.

Найдите минимальный вес среди всех триангуляций заданного многоугольника.

Вход. Одно целое число n (3 ≤ n ≤ 500) – количество вершин в правильном многоугольнике.

Выход. Выведите минимальный вес среди всех триангуляций заданного многоугольника.

Пример входа 1	Пример выхода 1
3	6
Пример входа 2	Пример выхода 2
4	18

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Рассмотрим треугольник, содержащий сторону (1, n). Пусть его третьей вершиной будет x, то есть рассматриваемый треугольник имеет вид (1, n, x).

Если x = n – 1, то отбросив треугольник (1, n, n – 1), перейдем к (n – 1) – угольнику.

Пусть 1 < x < n – 1. Рассмотрим треугольник (n, x, k), где x < k < n.

Заменим пару треугольников (1, x, n) и (n, x, k) на пару (1, x, k) и (1, n, k). Суммарный вес треугольников уменьшится, так как xn + xnk > xk + nk. После перегруппировки получим

x(n – k) + nk(x – 1) > 0

Неравенство справедливо, так как n – k > 0 и x – 1 > 0.

Отсюда следует, что треугольник (1, x, n) выгоднее заменить на (1, k, n), где k > x. Отсюда следует, что в качестве x выгодно взять x = n – 1. Триангуляция с минимальным весом получится, если провести все диагонали из вершины 1.

Минимальный вес равен

1 * 2 * 3 + 1 * 3 * 4 + … + 1 * (n – 1) * n =

Пример

В первом тесте задан треугольник с метками 1, 2, 3. Его вес равен 1 * 2 * 3 = 6.

Второй тест представляет собой квадрат с метками 1, 2, 3, 4. Минимальный вес получится для триангуляции, в которой проведена диагональ (1, 3). Он равен

1 * 2 * 3 + 1 * 3 * 4 = 6 + 12 = 18

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

Вычисляем ответ.

res = 0;

for (i = 2; i < n; i++)

res += 1ll * i * (i + 1);

Выводим ответ.

printf("%lld\n", res);